package list;

public class MergeLink {
    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(4);
        head.next.next = new Node(5);
        head.next.next.next = new Node(8);
        head.next.next.next.next = new Node(12);

        Node head2 = new Node(1);
        head2.next = new Node(5);
        head2.next.next = new Node(8);
        head2.next.next.next = new Node(18);
        head2.next.next.next.next = new Node(22);

        Node head3 = merge(head, head2);

        Node n = head3;
        while (n != null) {
            System.out.println(n.value);
            n = n.next;
        }
    }

    /*
        合并有序链表：
        两个有序链表的数据，依次比大小，小值连接到新链表中
        1.新建一个新链表的头部节点，preHead
        2.定义节点变量n1和n2，引用两个链表的头部节点
        3.定义节点变量n3，引用preHead
        4.进入循环，执行条件，n1和n2都在范围内 n1!=null n2!=null
        5.比较n1节点和n2节点中的值
        6.把较小值封装到一个新的节点对象，连接到n3后面
        7.n1和n2中较小的值的变量向后移动，n3也向后移动
        8.如果n1不是null，将n1直接连接到n3后面
        9.如果n2不是null，将n2直接连接到n3后面
        10.返回preHead.next
     */

    private static Node merge(Node head, Node head2) {
        Node preHead = new Node(0); //新建一个临时节点，以便向后连接其他节点
        Node n1 = head;
        Node n2 = head2;
        Node n3 = preHead;
        while (n1 != null && n2 != null) { //n1和n2都在界内
            if (n1.value < n2.value) { //n1节点是较小值
                n3.next = new Node(n1.value); //较小值放到新链表的末尾
                n1 = n1.next; //n1变量向后移动
            } else { //n2节点是较小值
                n3.next = new Node(n2.value);
                n2 = n2.next; //n2变量向后移动
            }
            n3 = n3.next; //n3向后移动到新连接的节点
        }

        //n3.next = n1; //n1节点连接到n3后面
        while (n1 != null) { //n1在界内
            n3.next = new Node(n1.value);
            n1 = n1.next;
            n3 = n3.next;
        }

        //n3.next = n2; //n2节点连接到n3后面
        while (n2 != null) { //n2在界内
            n3.next = new Node(n2.value);
            n2 = n2.next;
            n3 = n3.next;
        }
        return preHead.next; //临时节点的下一个是新链表的头部节点
    }

    static class Node {
        int value;

        Node prev;
        Node next;

        Node(int value) {
            this.value = value;
        }
    }
}









